package string;

/**
 * 给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。
 * 如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True ，否则返回 False 。
 * <p>
 * 示例 1：
 * 输入：s = "annabelle", k = 2
 * 输出：true
 * 解释：可以用 s 中所有字符构造 2 个回文字符串。
 * 一些可行的构造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"
 * <p>
 * 示例 2：
 * 输入：s = "leetcode", k = 3
 * 输出：false
 * 解释：无法用 s 中所有字符构造 3 个回文串。
 * <p>
 * 示例 3：
 * 输入：s = "true", k = 4
 * 输出：true
 * 解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。
 *
 * @author Jisheng Huang
 * @version 20250427
 */
public class ConstructKPalindromeStrings_1400 {
    /**
     * 1. 求出字符串 s 最少可以构造的回文串个数 left；
     * 2. 求出字符串 s 最多可以构造的回文串个数 right；
     * 3. 找出在 [left,right] 范围内满足要求的那些值，并判断 k 是否在其中。
     *
     * @param s the given string
     * @param k the number of the palindrome we need to construct
     * @return true if we can construct k palindrome
     */
    public static boolean canConstruct(String s, int k) {
        // 右边界
        int right = s.length();
        // 统计每个字符出现的次数
        int[] occ = new int[26];

        for (int i = 0; i < right; ++i) {
            ++occ[s.charAt(i) - 'a'];
        }

        // 左边界出现奇数次字符的个数
        int left = 0;

        for (int i = 0; i < 26; ++i) {
            if (occ[i] % 2 == 1) {
                ++left;
            }
        }

        left = Math.max(left, 1);

        return left <= k && k <= right;
    }

    public static void main(String[] args) {
        String s = "annabelle";
        int k = 2;

        System.out.println(canConstruct(s, k));

        s = "leetcode";
        k = 3;

        System.out.println(canConstruct(s, k));

        s = "true";
        k = 4;

        System.out.println(canConstruct(s, k));
    }
}